【题解】 Lunar New Year and Red Envelopes DP luoguCF1106E | Qiuly's blog!

【题解】 Lunar New Year and Red Envelopes DP luoguCF1106E

Posted on | In | Comments:

很简单的可以想到，设 $f_{i,j}$ 表示到第 $i$ 时刻已经干扰了 $j$ 次时的最少拿到钱数。然后每一次转移的时候只要看第 $i$ 时刻是否干扰即可，然后如果不干扰的话就算一下这一时刻拿到的红包的钱。

对于第 $i$ 时刻拿到的红包的钱数我们需要预处理，开一个优先队列，按照题意重载运算符，然后按照时刻走一遍即可。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1e5+3;
const int M=2e2+3;

ll f[N][M];
int n,m,k,nxt[N],val[N];
struct Node {
    int s,t,d,w,id;
    bool operator < (const Node&b) const {return w==b.w?b.d>d:b.w>w;}
}a[N];
priority_queue<Node> q;

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

bool cmp(Node x,Node y) {return x.s<y.s;}

int main() {
    IN(n),IN(m),IN(k);
    for(int i=1;i<=k;++i)
        IN(a[i].s),IN(a[i].t),IN(a[i].d),IN(a[i].w),a[i].id=i;
    sort(a+1,a+1+k,cmp);
    int cnt=1;
    for(int i=0;i<=n;++i) {
        while(cnt<=k&&a[cnt].s<=i) q.push(a[cnt++]);
        if(q.empty()) nxt[i]=i+1,val[i]=0;
        else {
            Node now=q.top();
            if(now.t<i) {--i,q.pop();continue;}
            nxt[i]=now.d+1,val[i]=now.w;
        }
    }
    memset(f,127,sizeof(f));
    f[0][0]=0;
    for(int i=0;i<=n;++i)for(int j=0;j<=m;++j)
        f[i+1][j+1]=min(f[i+1][j+1],f[i][j]),
        f[nxt[i]][j]=min(f[nxt[i]][j],f[i][j]+val[i]);
    ll ans=1e18+9;
    for(int i=0;i<=m;++i) ans=min(ans,f[n+1][i]);
    printf("%lld\n",ans);
    return 0;
}

本文标题:【题解】 Lunar New Year and Red Envelopes DP luoguCF1106E

文章作者:Qiuly

发布时间:2019年05月22日 - 00:00

最后更新:2019年05月22日 - 13:35

原始链接:http://qiulyblog.github.io/2019/05/22/[题解]luoguCF1106E/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。